import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class WordBreak2 {

    List<String> list = new ArrayList<>();
    List<String> ans = new ArrayList<>();
    public List<String> wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], true);
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i ; j < n; j++) {
                dp[i][j] = wordDict.contains(s.substring(i, j + 1));
            }
        }
        process(dp, 0, s);
        return ans;
    }

    public void process(boolean[][] dp, int i, String s) {
        if (i == s.length()) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int j = 0; j < list.size() - 1; j++) {
                stringBuilder.append(list.get(i) + " ");
            }
            stringBuilder.append(list.get(list.size() - 1));
            ans.add(stringBuilder.toString());
            return;
        }
        for (int j = i; j < s.length(); j++) {
            if (dp[i][j]) {
                list.add(s.substring(i, j + 1));
                process(dp, j + 1, s);
                list.remove(list.size() - 1);
            }
        }
    }
}
